package com.zhanghp.class05;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href = "https://leetcode.com/problems/merge-k-sorted-lists"/>合并k个有序列表</a>
 *
 * @author zhanghp
 * @since 2023/11/20 10:01
 */
public class Code01_MergetKSortedLists {

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new ComparatorListNode());
        for (ListNode it : lists) {
            if (it != null) {
                queue.add(it);
            }
        }
        if (queue.isEmpty()) {
            return null;
        }
        ListNode poll = queue.poll();
        if (poll.next != null) {
            queue.add(poll.next);
        }
        ListNode listNode = poll;
        while (!queue.isEmpty()) {
            ListNode p = queue.poll();
            listNode.next = p;
            listNode = p;
            if (p.next != null) {
                queue.add(p.next);
            }
        }
        return poll;
    }

    public static ListNode[] generate(int arrayMaxLength, int childMaxLength, int maxVal) {
        int length = ((int) (Math.random() * arrayMaxLength)) + 1;
        ListNode[] result = new ListNode[length];
        for (int i = 0; i < result.length; i++) {
            result[i] = generate(childMaxLength, maxVal);
        }
        return result;
    }

    public static ListNode generate(int maxLength, int maxVal) {
        int length = ((int) (Math.random() * maxLength)) + 1;
        ListNode listNode = new ListNode(((int) (Math.random() * maxVal)) + 1);
        ListNode temp = listNode;
        --length;
        for (int i = 0; i < length; i++) {
            int val = ((int) (Math.random() * maxVal)) + 1;
            temp.next = new ListNode(val);
            temp = temp.next;
        }
        return listNode;
    }

    public static void main(String[] args) {
        ListNode[] generate = generate(5, 3, 10);
        System.out.println("ListNode[] :");
        print(generate);
        ListNode listNode = mergeKLists(generate);
        System.out.println("Merge K List ：");
        print(listNode);
    }


    private static void print(ListNode[] listNodes) {
        if (listNodes == null) {
            System.out.printf("%s", "数组为空");
        }
        for (int i = 0; i < listNodes.length; i++) {
            System.out.printf("%s", i + ":");
            print(listNodes[i]);
            System.out.println();
        }
    }

    private static void print(ListNode listNodes) {
        if (listNodes == null) {
            System.out.printf("%s", "空");
        }
        do {
            System.out.print(listNodes.val + ",");
            listNodes = listNodes.next;
        } while (listNodes != null);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static class ComparatorListNode implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

}
